【week12】452. Minimum Number of Arrows to Burst Balloons 解题报告

452. Minimum Number of Arrows to Burst Balloons

题目

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most $10^4$ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with $x_{start}$ and $x_{end}$ bursts by an arrow shot at x if $x_{start} \le x \le x_{end}$. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

解题报告

题意很简单，找出能落在所有区间 [start, end] 的数字集合的最小大小。

见到这道题第一反应就是先把最简单的情况排除掉，就是当区间数 <= 1 时，只要返回区间数就好了。

然后自然就要先做排序，我刚开始的 key 是 start。看到题目的 tag 是贪心，自然就往简单的解法上靠。

第一次的解法是判断当前区间与前一个有没有重叠，如果没有就让 ans 加一，但是这有个问题，如果一个区间头尾都与相邻区间重叠的话就会出问题了。

然后我的第二种解法是，记下集合里最后一个数字，如果 last < start，就把这个数字更新为当前区间的 end，同时 ans 加一。但是这又有一个问题，如果上一个区间包含当前区间的话，且最后一个数字就是上一个区间的 end 时，就会导致重复。

既然现在问题是当前 end 可能小于上一个 end，那我按 end 排序不就好了吗？把 key 一改，果然 a 掉。

那么问题来了，为什么可以这么做呢？

• 首先按照 end 排序，每次只选择 end 为集合元素可以理解为尽量靠近下一个区间，这样落在下一个区间的可能性也会更大，但如果这样都不能命中下一个区间的话，那说明当前集合不能命中下一个区间，只能为下一个区间额外添加一个元素。这也是这个解法的 “贪心” 之处。
• last 为什么只需要大于 start 呢？因为如果 last > end ，就说明当前区间 end > prev_end ，这是不可能的。

Solution

class Solution {
public:
    int findMinArrowShots(vector<pair<int, int>>& points) {
        if (points.size() < 2) {
            return points.size();
        }
        sort(points.begin(), points.end(), 
             [](const pair<int, int> &p1, const pair<int, int> &p2) { return p1.second < p2.second; });
        
        int arrow = 0, x = INT_MIN;
        for (int i = 0; i < points.size(); ++i) {
            if (points[i].first <= x) continue;
            ++arrow;
            x = points[i].second;
        }
        return arrow;
    }
};